#encoding=utf-8

'''
[54,26,93,17,77,31,44,55]

[54,26,93,17] [77,31,44,55]

[54,26] [93,17] [77,31] [44,55]

[54] [26] [93] [17] [77] [31] [44] [55]

合并
[26,54] [17, 93] [31, 77] [44,55]

[17,26,54,93]  [31,44,55,77]

[17,26,31,44,54,55,77,93]
'''

def mer_sort(alist):
    n = len(alist)
    #递归的出口
    if n<=1:
        return alist
    mid = n//2
    left_li=mer_sort(alist[0:mid])
    right_li=mer_sort(alist[mid:])

    #合并
    #排序结果列表
    result=[]
    left_pointer,right_pointer=0,0

    while left_pointer<len(left_li) and right_pointer<len(right_li):
        if left_li[left_pointer]<=right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer+=1
        else:
            result.append(right_li[right_pointer])
            right_pointer+=1

    #退出循环后，将不为空的列表剩余元素添加到result中
    # result+=left_li[left_pointer:]
    result.extend(left_li[left_pointer:])
    result+=right_li[right_pointer:]

    return result

if __name__ == "__main__":
    alist=[54,26,93,17,77,31,44,55]
    result=mer_sort(alist)
    print("合并排序后的列表：",result)

#时间复杂度：最坏：O(nlogn)；最优：O(nlogn) 稳定